package com.zzh.tree;

import java.util.HashMap;
import java.util.Map;

public class No106_buildTree {
    public static void main(String[] args) {
        No106Solution solution = new No106Solution();
        TreeNode treeNode = solution.buildTree(new int[]{9, 3, 15, 20, 7}, new int[]{9, 15, 7, 20, 3});
        TreeNode.printTree(treeNode);
    }
}
class No106Solution{
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int inLen=inorder.length;
        int postLen=postorder.length;
        Map<Integer,Integer> map=new HashMap<>();
        for (int i=0;i<inLen;i++){
            map.put(inorder[i],i);
        }
        return build(postorder,0,postLen-1,map,0,inLen-1);
    }

    private TreeNode build(int[] postorder,
                           int postLeft, int postRight,
                           Map<Integer, Integer> map,
                           int inLeft, int inRight) {
        if (postLeft>postRight||inLeft>inRight){
            return null;
        }
        int rootVal=postorder[postRight];
        TreeNode root=new TreeNode(rootVal);
        int pIndex=map.get(rootVal);
        root.left=build(postorder,postLeft,pIndex-inLeft+postLeft-1,
                map,
                inLeft,pIndex-1);
        root.right=build(postorder,pIndex-inLeft+postLeft,postRight-1,
                map,
                pIndex+1,inRight);
        return root;

    }
}
